package org.cinvestav.computacion.matias.onlyangel.grafo;

import java.util.ArrayList;

public class RecorreElGrafo {
	public int margenes[][];
	public Matriz m = new Matriz();
	Grafo g = null;
	int pesos[];
	PilaRuta r = new PilaRuta(), rB = new PilaRuta();
	int h,w,xo,yo,x1,y1;

	HiloController controllador;

	int solopruebas;
	public RecorreElGrafo(Matriz ma,int h, int w, int x0, int y0, int x, int y, HiloController hlo) {
		controllador = hlo;
		//int w,h;
		this.h =h;
		this.w = w;
		xo = x0;
		yo = y0;
		x1 = x;
		y1 = y;
		Contenedor origenX  = new Contenedor(x0);
		Contenedor origenY  = new Contenedor(y0);
		Contenedor destinoX = new Contenedor(x);
		Contenedor destinoY = new Contenedor(y);

		m = ma.acotada(x0, y0, x, y, origenX, origenY, destinoX, destinoY);
		
		xo = origenX.valor;
		yo = origenY.valor;
		x1 = destinoX.valor;
		y1 = destinoY.valor;

		/*
		m = ma.acotada(xo, yo, x1, y1);

		xo = x0;
		yo = y0;
		x1 = x;
		y1 = y;
		 */
		rB.sum = m.suma();

		pesos=m.getPesos();

		margenes = new int[h][w];

		g = new Grafo(m);
		g.print();
	}

	public void recorreSimple(int x1, int y1, int x2, int y2){
		int origen=m.arr[y1][x1].pos, destino=m.arr[y2][x2].pos;
		recorreSimpleRecur(origen,destino);
	}

	public void recorreSimpleRecur(int origen, int destino){
		if (solopruebas++%1000000==0)
			System.out.println("Muchas iteracciones");

		if (r.add(new Integer(origen), new Integer(pesos[origen]))){

			if (origen==destino){
				if ((rB.sum==0)||(rB.sum>r.sum)){
					r.print();
					rB = new PilaRuta(r);


				}
			}else{
				for (int n=0 ; n<g.size;n++)
					if (g.grafo[origen][n].sino)
						recorreSimpleRecur(n,destino);
			}
			r.del();
		}
	}


	public void miRecorreSimple(){
		int x1 = xo;
		int y1= yo;
		int x2 = this.x1;
		int y2 = this.y1;
		int origen=m.arr[y1][x1].pos, destino=m.arr[y2][x2].pos;
		//miRecorreRecur02(origen,destino);
		miRecorreRecur03(origen,destino,origen,origen);
		controllador.finalizado();
		System.out.println("El mejor:");
		rB.print();

		System.out.println("Fue el anterior "+new Long(rB.sum).toString()+" con "+new Integer(solopruebas).toString()+" iteraciones.");
	}

	public void miRecorreRecur(int origen, int destino){
		ArrayList<Integer> tempList = new ArrayList<Integer>();

		if (solopruebas++%1000000==0){
			System.out.println("Muchas iteracciones");
			//r.print();
		}

		if (r.add(new Integer(origen), new Integer(pesos[origen]))){

			if (origen==destino){
				if ((rB.sum==0)||(rB.sum>r.sum)){
					r.print();
					rB = new PilaRuta(r);
				}
			}else{
				for (int n=0 ; n<g.size;n++)
					if (g.grafo[origen][n].sino)
						//miRecorreRecur(n,destino);
						tempList.add(new Integer(n));
				Integer t = null;
				for (int n=0;n<tempList.size()-1;n++){
					for (int u=n+1;u<tempList.size();u++){
						if (g.grafo[origen][tempList.get(u).intValue()].val<g.grafo[origen][tempList.get(n).intValue()].val){
							t = tempList.get(u);
							tempList.set(u, tempList.get(n));
							tempList.set(n, t);
						}
					}
					miRecorreRecur(tempList.get(n).intValue(),destino);
				}
			}
			r.del();
		}
	}

	public void miRecorreRecur02(int origen, int destino){
		ArrayList<Integer> tempList = new ArrayList<Integer>();

		if (++solopruebas%1000000==0){
			System.out.println("Muchas iteracciones");
			//r.print();
		}

		if (r.add(new Integer(origen), new Integer(pesos[origen]))){

			if (origen==destino){
				if ((rB.sum==0)||(rB.sum>r.sum)){
					r.print();
					rB = new PilaRuta(r);
				}
			}else{
				for (int n=0 ; n<g.size;n++)
					if (g.grafo[origen][n].sino)
						//miRecorreRecur(n,destino);
						tempList.add(new Integer(n));
				Integer t = null;
				for (int n=0;n<tempList.size()-1;n++){
					for (int u=n+1;u<tempList.size();u++){
						if (g.grafo[origen][tempList.get(u).intValue()].val<g.grafo[origen][tempList.get(n).intValue()].val){
							t = tempList.get(u);
							tempList.set(u, tempList.get(n));
							tempList.set(n, t);
						}
					}
					if (g.grafo[origen][tempList.get(n).intValue()].val+r.sum<=rB.sum)
						miRecorreRecur02(tempList.get(n).intValue(),destino);
				}
			}
			r.del();
		}
	}

	public void miRecorreRecur03(int origen, int destino, int a1, int a2){
		if (controllador.continua()){
			ArrayList<Integer> tempList = new ArrayList<Integer>();

			if (++solopruebas%1000000==0){
				System.out.println("Muchas iteracciones");
				//r.print();
			}

			if (r.add(new Integer(origen), new Integer(pesos[origen]))){

				if (a1!=a2)
					addMargenes(g.grafo[a2][a1].x, g.grafo[a2][a1].y);

				if (origen==destino){
					if ((rB.sum==0)||(rB.sum>r.sum)){
						r.print();
						rB = new PilaRuta(r);
					}
				}else{
					for (int n=0 ; n<g.size;n++)
						if (g.grafo[origen][n].sino)
							//miRecorreRecur(n,destino);
							tempList.add(new Integer(n));
					Integer t = null;
					for (int n=0;n<tempList.size();n++){
						for (int u=n;u<tempList.size();u++){
							if (g.grafo[origen][tempList.get(u).intValue()].val<g.grafo[origen][tempList.get(n).intValue()].val){
								t = tempList.get(u);
								tempList.set(u, tempList.get(n));
								tempList.set(n, t);
							}
						}
						if (margenes[g.grafo[origen][tempList.get(n).intValue()].y][g.grafo[origen][tempList.get(n).intValue()].x]==0){
							if (g.grafo[origen][tempList.get(n).intValue()].val+r.sum<=rB.sum){

								miRecorreRecur03(tempList.get(n).intValue(), destino, origen, a1);

							}
						}
					}
				}

				if (a1!=a2)
					delMargenes(g.grafo[a2][a1].x, g.grafo[a2][a1].y);

				r.del();
			}
		}
	}

	public void addMargenes(int x,int y){
		if ( (y-1>=0)&&(x-1>=0)){
			margenes[y-1][ x-1]++;
		}

		if ((y-1>=0)){
			margenes[y-1][ x]++;
		}

		if ((y-1>=0)&&(x+1<m.w)){
			margenes[y-1] [x+1]++;
		}

		if ((x-1>=0)){
			margenes[y][x-1]++;
		}

		if ((x+1<m.w)){
			margenes[y] [x+1]++;
		}

		if ((y+1<m.h)&&(x-1>=0)){
			margenes[y+1] [x-1]++;
		}

		if ((y+1<m.h)){
			margenes[y+1][ x]++;
		}

		if ((y+1<m.h)&&(x+1<m.w)){
			margenes[y+1] [x+1]++;
		}
		margenes[y][x]++;
	}

	public void delMargenes(int x,int y){
		if ( (y-1>=0)&&(x-1>=0)){
			margenes[y-1][ x-1]--;
		}

		if ((y-1>=0)){
			margenes[y-1][ x]--;
		}

		if ((y-1>=0)&&(x+1<m.w)){
			margenes[y-1] [x+1]--;
		}

		if ((x-1>=0)){
			margenes[y][x-1]--;
		}

		if ((x+1<m.w)){
			margenes[y] [x+1]--;
		}

		if ((y+1<m.h)&&(x-1>=0)){
			margenes[y+1] [x-1]--;
		}

		if ((y+1<m.h)){
			margenes[y+1][ x]--;
		}

		if ((y+1<m.h)&&(x+1<m.w)){
			margenes[y+1] [x+1]--;
		}
		margenes[y][x]--;
	}

	/**
	 * @param args
	 */


}
